﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace Chapter_9__Recursion_
{
    public static class Ex_9_6
    {
        static bool UseDynamicProgramming = true;

        public static SortedSet<string> GetAllParenthesesPermutations(int NumPairs)
        {
            if (NumPairs <= 0)
            {
                SortedSet<string> newSet = new SortedSet<string>();
                newSet.Add("");
                return new SortedSet<string>(newSet);
            }
            else if (NumPairs == 1)
            {
                SortedSet<string> newSet = new SortedSet<string>();
                newSet.Add("()");
                return new SortedSet<string>(newSet);
            }

            SortedSet<string> resultSet = GetAllParenthesesPermutations(NumPairs - 1);
            SortedSet<string> newResultSet = new SortedSet<string>();

            foreach (string result in resultSet)
            {
                for (int i = 0; i < result.Length; i++)
                {
                    if (result[i] == '(')
                    {
                        string newString = result.Insert(i + 1, "()");
                        newResultSet.Add(newString);
                    }
                }
                newResultSet.Add("()" + result);

                // The following was wrong...
                // It could not produce (())(()), for example.
                //string left = "()" + result;
                //string right = result + "()";
                //string surrounding = "(" + result + ")";

                //newResultSet.Add(left);
                //newResultSet.Add(surrounding);
                //if (left != right)
                //    newResultSet.Add(right);
            }

            return newResultSet;
        }
    }
}
